import collections


class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        k = n // 3
        d = collections.defaultdict(int)
        out = []
        for i in range(k):
            new_d = collections.defaultdict(int)
            for key in d:
                if d[key] > 1:
                    new_d[key] = d[key] - 1
            for j in range(3):
                new_d[nums[3 * i + j]] += 1
            d = new_d
        if k * 3 < n:
            new_d = collections.defaultdict(int)
            for key in d:
                if d[key] > 1:
                    new_d[key] = d[key] - 1
            for j in range(3 * k, n):
                new_d[nums[j]] += 1
            d = new_d
        for key in d:
            if nums.count(key) > k:
                out.append(key)
        out.sort()
        return out


data = Solution()
nums = [3, 2, 3]
print(data.majorityElement(nums))
nums = [1, 2]
print(data.majorityElement(nums))
nums = [1]
print(data.majorityElement(nums))
